
#include <stdio.h>
#include <list>

#include <stdlib.h>
#include <unistd.h>

#define M 20

void dump(int a[M][M])
{
    int i, j;
    printf("-------------------------------\n");
    for (i = 0; i < M; i++) {
        for (j = 0; j < M; j++) {
            if (a[i][j] == -1) {
                printf("  ");
            } else if (a[i][j] == -2) {
                printf("* ");
            } else {
                printf("%d ", a[i][j]);
            }
        }
        printf("\n");
    }
    printf("-------------------------------\n");
}

void init(int a[M][M])
{
    int i, j;
    for (i = 0; i < M; i++) {
        for (j = 0; j < M; j++) {
            a[i][j] = -1;
        }
    }
    a[9][9] = -2;
    a[11][9] = -2;
    a[10][9] = -2;
}

class Point
{
public:
    Point(int _x, int _y) : x(_x), y(_y) {}
    int x;
    int y;
};

bool usable(int a[M][M], int x, int y)
{
    if (x < 0 || x >= M)
        return false;
    if (y < 0 || y >= M)
        return false;
    return true;
}

bool check_and_put_distance(int a[M][M], int x, int y, int distance)
{
    if (a[x][y] > distance || a[x][y] == -1) {
        a[x][y] = distance;
        return true;
    }
    return false;
}

void calc(int a[M][M], int x, int y, int step)
{
    init(a);

    std::list<Point>    l;
    l.push_back(Point(x, y));

    a[x][y] = 0;
    while (!l.empty()) {
        Point   pt = l.front();
        l.pop_front();

        int distance = a[pt.x][pt.y];

        if (usable(a, pt.x - 1, pt.y) && distance < step) {
            if (check_and_put_distance(a, pt.x - 1, pt.y, distance + 1))
                l.push_back(Point(pt.x - 1, pt.y));
        }
        if (usable(a, pt.x + 1, pt.y) && distance < step) {
            if (check_and_put_distance(a, pt.x + 1, pt.y, distance + 1))
                l.push_back(Point(pt.x + 1, pt.y));
        }
        if (usable(a, pt.x, pt.y - 1) && distance < step) {
            if (check_and_put_distance(a, pt.x, pt.y - 1, distance + 1))
                l.push_back(Point(pt.x, pt.y - 1));
        }
        if (usable(a, pt.x, pt.y + 1) && distance < step) {
            if (check_and_put_distance(a, pt.x, pt.y + 1, distance + 1))
                l.push_back(Point(pt.x, pt.y + 1));
        }

        /*
        system("clear");
        dump(a);
        printf("%lu\n", l.size());
        for (std::list<Point>::iterator it = l.begin(); it != l.end(); it++) {
            printf("(%d, %d) ", (*it).x, (*it).y);
        }
        printf("\n");
        usleep(500000);
        */
    }
}

int main()
{
    int a[M][M] = {{0, 0}};

    calc(a, 10, 10, 5);

    dump(a);

    return 0;
}


